﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PancakeSorting.Model
{
    public class PancakeSort
    {
        private List<int> _sortingList;
        public List<int> SortingList
        {
            get { return _sortingList; }
            set { _sortingList = value; }
        }

        private string _sortedListToString;
        public string SortedListToString
        {
            get { return _sortedListToString; }
            set { _sortedListToString = value; }
        }

        private string _log;
        public string Log
        {
            get { return _log; }
            set { _log = value; }
        }

        #region Constructors
        public PancakeSort()
        {
            SortingList = null;
            SortedListToString = "";
            Log = "";
        }

        public PancakeSort(List<int> SortingList)
        {
            this.SortingList = SortingList;
            SortedListToString = "";
            Log = "";
        }

        public PancakeSort(string stringList)
        {
            string[] parameters = stringList.Split(' ');
            int[] values = new int[parameters.Length];
            for (int i = 0; i < values.Length; i++)
            {
                values[i] = int.Parse(parameters[i]);   
            }
            SortingList = new List<int>(values);
            SortedListToString = "";
            Log = "";
        }
        #endregion

        /// <summary>
        /// Método principal de sort que realizará a ordenação da
        /// lista contida na variável SortingList. Ao final de sua
        /// execução, o método passará para a variável SortedListToString
        /// o valor string da lista ordenada.
        /// 
        /// O resultado é dado em ordem crescente.
        /// 
        /// </summary>
        /// <returns></returns>
        public List<int> Sort()
        {
           //Inicialmente o Log é limpo para não manter valores das ordenações anteriores
            Log = "";
            //Inicia o Log com a data atual e a string correspondente a lista que será ordenada
            Log += DateTime.Now.ToString()+ "- Sorting:" +ListToString(SortingList);

            //Verificação trivial, caso a lista só possua uma entrada ou já esteja ordenada
            //o método retorna a própria lista e seta a variável SortedListToString para ser
            //seu valor em string, como usual
            if (SortingList.Count <= 1 || CheckSort())
            {
                SortedListToString = ListToString();
                return SortingList;
            }

            //Realizada uma cópia profunda da lista a ser ordenada para preservar 
            //sua configuração inicial
            List<int> sortedList = CloneList(SortingList);

            int ignoredIndex = 0;
            //Essa variável serve para guardar o número do passo no Log
            int step = 1;

            //O primeiro passo é diferente dos demais, nele, vamos procurar o menor

            //Descrito  o número do passo no Log
            Log += "\r\n------------------------\r\nPasso nº " + step + "\r\n";

            int lesserIndex = LesserIndex(sortedList, ignoredIndex);

            //Escrito no Log o valor do menor index e seu valor correspondente na lista
            Log += "\r\nMenor index = " + lesserIndex + "\r\nValor do menor index = " + sortedList[lesserIndex];

            //Escrito no Log a situação atual da lista antes da inversão
            Log += "\r\nLista antes da inversão: " + ListToString(sortedList);

            InvertListAtIndexToIndex(sortedList, ignoredIndex, lesserIndex);

            //Escrito no Log a situação atual da lista após a inversão
            Log += "\r\nLista depois da inversão: " + ListToString(sortedList);

            ignoredIndex++;
            step++;

            while (!CheckSort(sortedList))
            {
                //Descrito  o número do passo no Log
                Log += "\r\n------------------------\r\nPasso nº " + step + "\r\n";

                if (ignoredIndex >= sortedList.Count)
                {
                    new Exception("Erro, ignored index ficou muito alto!");
                }

                lesserIndex = LesserIndex(sortedList, ignoredIndex);

                //Escrito no Log o valor do menor index e seu valor correspondente na lista
                Log += "\r\nMenor index = " + lesserIndex + "\r\nValor do menor index = " + sortedList[lesserIndex];

                //Escrito no Log a situação atual da lista antes da inversão
                Log += "\r\nLista antes da inversão:  " + ListToString(sortedList);

                if (lesserIndex == step - 1)
                {
                    Log += "\r\nElemento já está ordenado!";

                    //Escrito no Log a situação atual da lista com elementos já ordenados
                    Log += "\r\nLista:  " + ListToString(sortedList);
                }
                else
                {
                    InvertListAtIndexToIndex(sortedList, lesserIndex, sortedList.Count - 1);
                    //Escrito no Log a situação atual da lista após a inversão que coloca o 
                    //menor elemento no topo
                    Log += "\r\nLista depois da inversão (1): " + ListToString(sortedList);

                    InvertListAtIndexToIndex(sortedList, ignoredIndex, sortedList.Count - 1);
                    //Escrito no Log a situação atual da lista após a inversão que coloca o 
                    //menor elemento depois do ignored index
                    Log += "\r\nLista depois da inversão (2): " + ListToString(sortedList);
                }
                ignoredIndex++;
                step++;

                Log += "\r\n------------------------";
            }

            SortedListToString = ListToString(sortedList);
            return sortedList;
        }

        /// <summary>
        /// Método para verificar se determinada lista já se encontra ordenada.
        /// Esse processo verifica se algum item de index I é maior do que o 
        /// item de index I + 1.
        /// 
        /// </summary>
        /// <returns></returns>
        private bool CheckSort()
        {
            return CheckSort(SortingList);
        }

        /// <summary>
        /// Método para verificar se determinada lista já se encontra ordenada.
        /// Esse processo verifica se algum item de index I é maior do que o 
        /// item de index I + 1.
        /// 
        /// </summary>
        /// <returns></returns>
        private bool CheckSort(List<int> list)
        {
            for (int i = 0; i < list.Count - 1; i++)
            {
                if (list[i] > list[i + 1])
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// Método baseado em uma contagem a partir do 0.
        /// 
        /// Retorna o index do menor elemento da lista, por exemplo:
        /// Para a lista = {3 4 2 1 5}
        /// O resultado será o index 3, correspondente ao número 1
        /// 
        /// </summary>
        /// <returns></returns>
        private int LesserIndex()
        {
            return LesserIndex(SortingList);
        }

        /// <summary>
        /// Método baseado em uma contagem a partir do 0.
        /// 
        /// Retorna o index do menor elemento da lista, por exemplo:
        /// Para a lista = {3 4 2 1 5}
        /// O resultado será o index 3, correspondente ao número 1
        /// 
        /// </summary>
        /// <returns></returns>
        private int LesserIndex(List<int> list)
        {
            int lesser = list[0];
            int index = 0;

            for (int i = 0; i < list.Count; i++)
            {
                if (lesser > list[i])
                {
                    lesser = list[i];
                    index = i;
                }
            }
            return index;
        }

        /// <summary>
        /// Método baseado em uma contagem a partir do 0.
        /// 
        /// Retorna o index do menor elemento da lista, no entanto,
        /// ignora todos os valores até o valor do ignoredIndex (inclusive)
        /// que é passado como parâmetro, por exemplo:
        /// Para a lista = {1 4 2 3 5} e ignoredIndex = 1
        /// O resultado será o index 2, correspondente ao número 2, ignorando o valor 1
        /// 
        /// </summary>
        /// <returns></returns>
        private int LesserIndex(List<int> list, int ignoredIndex)
        {
            int lesser = list[ignoredIndex];
            int index = ignoredIndex;

            for (int i = ignoredIndex; i < list.Count; i++)
            {
                if (lesser > list[i])
                {
                    lesser = list[i];
                    index = i;
                }
            }
            return index;
        }

        /// <summary>
        /// Método baseado em uma contagem a partir do 0.
        /// 
        /// O index passado deve ser correspondente ao início do ponto de inversão, por exemplo:
        /// 
        /// Para o index = 2 e lista = {1 2 3 4 5}
        /// O resultado será a lista = {1 2 5 4 3}
        /// 
        /// </summary>
        /// <param name="list"></param>
        /// <param name="index"></param>
        private void InvertListAtIndex(List<int> list, int index)
        {
            int initial = index;
            int final = list.Count - 1;
            //Variável para auxiliar no swap das posições
            int aux = 0;

            //Se o index corresponder ao ultimo elemento da lista, então
            //é realizada uma inversão da lista toda, ou seja, a posição
            //inicial passa a ser o index 0
            if (index == list.Count - 1)
            {
                initial = 0;
            }

            while (initial < final)
            {
                aux = list[final];
                list[final] = list[initial];
                list[initial] = aux;

                initial++;
                final--;
            }
        }

        /// <summary>
        /// Método baseado em uma contagem a partir do 0.
        /// 
        /// Método para inverter sublistas dentro de uma lista principal, por exemplo:
        /// Para a lista = {1 2 3 5 4}, a initial = 3 e final = 4
        /// O resultado será a lista = {1 2 3 4 5}
        /// 
        /// </summary>
        /// <param name="list"></param>
        /// <param name="initial"></param>
        /// <param name="final"></param>
        private void InvertListAtIndexToIndex(List<int> list, int initial, int final)
        {
            //Variável para auxiliar no swap das posições
            int aux = 0;

            while (initial < final)
            {
                aux = list[final];
                list[final] = list[initial];
                list[initial] = aux;

                initial++;
                final--;
            }
        }

        /// <summary>
        /// Método para retornar a string correspondente a uma lista de ints, por exemplo:
        /// Para a lista = {1 2 3 4}
        /// O resultado é a a string "{1  2  3  4  }  
        /// 
        /// </summary>
        /// <returns></returns>
        private string ListToString()
        {
            return ListToString(SortingList);
        }

        /// <summary>
        /// Método para retornar a string correspondente a uma lista de ints, por exemplo:
        /// Para a lista = {1 2 3 4}
        /// O resultado é a a string "{1  2  3  4  }  
        /// 
        /// </summary>
        /// <returns></returns>
        private string ListToString(List<int> list)
        {
            string toString = "{";
            for (int i = 0; i < list.Count; i++)
            {
                toString += list[i] + "  ";
            }
            toString += "}";

            return toString;
        }

        /// <summary>
        /// Método para realizar cópia profunda de uma lista passada como parâmetro.
        /// 
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        private List<int> CloneList(List<int> target)
        {
            List<int> clone = new List<int>();
            for (int i = 0; i < target.Count; i++)
            {
                clone.Add(target[i]);
            }
            return clone;
        }
    }
}
